Lucas sequence

In mathematics, the Lucas sequences Un(P,Q) and Vn(P,Q) are certain integer sequences that satisfy the recurrence relation

xn = Pxn-1 - Qxn-2

where P and Q are fixed integers. Any other sequence satisfying this recurrence relation can be represented as a linear combination of the Lucas sequences Un(P,Q) and Vn(P,Q).

More generally, Lucas sequences Un(P,Q) and Vn(P,Q) represent sequences of polynomials in P and Q with integer coefficients.

Famous examples of Lucas sequences include the Fibonacci numbers, a superset of the Fermat numbers, Mersenne numbers, Pell numbers, Lucas numbers and Jacobsthal numbers. Lucas sequences are named after the French mathematician Édouard Lucas.

Contents

Recurrence relations

Given two integer parameters P and Q, the Lucas sequences of the first kind Un(P,Q) and of the second kind Vn(P,Q) are defined by the recurrence relations:

U_0(P,Q)=0, \,
U_1(P,Q)=1, \,
U_n(P,Q)=P\cdot U_{n-1}(P,Q)-Q\cdot U_{n-2}(P,Q) \mbox{  for }n>1, \,

and

V_0(P,Q)=2, \,
V_1(P,Q)=P, \,
V_n(P,Q)=P\cdot V_{n-1}(P,Q)-Q\cdot V_{n-2}(P,Q) \mbox{  for }n>1, \,

It is not hard to show that for n>0,

U_n(P,Q)=\frac{P\cdot U_{n-1}(P,Q) %2B V_{n-1}(P,Q)}{2},  \,
V_n(P,Q)=\frac{(P^2-4Q)\cdot U_{n-1}(P,Q)%2BP\cdot V_{n-1}(P,Q)}{2}.  \,

Examples

Initial terms of Lucas sequences Un(P,Q) and Vn(P,Q) are given in the table:

n\, U_n(P,Q)\, V_n(P,Q)\,
0\, 0\, 2\,
1\, 1\, P\,
2\, P\, {P}^{2}-2Q\,
3\, {P}^{2}-Q\, {P}^{3}-3PQ\,
4\, {P}^{3}-2PQ\, {P}^{4}-4{P}^{2}Q%2B2{Q}^{2}\,
5\, {P}^{4}-3{P}^{2}Q%2B{Q}^{2}\, {P}^{5}-5{P}^{3}Q%2B5P{Q}^{2}\,
6\, {P}^{5}-4{P}^{3}Q%2B3P{Q}^{2}\, {P}^{6}-6{P}^{4}Q%2B9{P}^{2}{Q}^{2}-2{Q}^{3}\,

Algebraic relations

The characteristic equation of the recurrence relation for Lucas sequences U_n(P,Q) and V_n(P,Q) is:

x^2 - Px %2B Q=0 \,

It has the discriminant D=P^2 - 4Q and the roots:

a = \frac{P%2B\sqrt{D}}2\quad\text{and}\quad b = \frac{P-\sqrt{D}}2. \,

Thus:

a %2B b = P\, ,
a b = \frac{1}{4}(P^2 - D) = Q\, ,
a - b = \sqrt{D}\, .

Note that the sequence a^n and the sequence b^n also satisfy the recurrence relation. However these might not be integer sequences.

Distinct roots

When D\ne 0, a and b are distinct and one quickly verifies that

a^n = \frac{V_n %2B U_n \sqrt{D}}{2}
b^n = \frac{V_n - U_n \sqrt{D}}{2}.

It follows that the terms of Lucas sequences can be expressed in terms of a and b as follows

U_n= \frac{a^n-b^n}{a-b} = \frac{a^n-b^n}{ \sqrt{D}}
V_n=a^n%2Bb^n \,

Repeated root

The case  D=0 occurs exactly when  P=2S \text{ and }Q=S^2 for some integer S so that a=b=S. In this case one easily finds that

U_n(P,Q)=U_n(2S,S^2) = nS^{n-1}\,
V_n(P,Q)=V_n(2S,S^2)=2S^n\,.

Other relations

The terms of Lucas sequences satisfy relations that are generalizations of those between Fibonacci numbers F_n=U_n(1,-1) and Lucas numbers L_n=V_n(1,-1). For example:

General P = 1, Q = -1
(P^2-4Q) U_n = {V_{n%2B1} - Q V_{n-1}}=2V_{n%2B1}-P V_n \, 5F_n = {L_{n%2B1} %2B L_{n-1}}=2L_{n%2B1} - L_{n} \,
V_n = U_{n%2B1} - Q U_{n-1}=2U_{n%2B1}-PU_n \, L_n = F_{n%2B1} %2B F_{n-1}=2F_{n%2B1}-F_n \,
U_{2n} = U_n V_n \, F_{2n} = F_n L_n \,
V_{2n} = V_n^2 - 2Q^n \, L_{2n} = L_n^2 - 2(-1)^n \,
U_{n%2Bm} = U_n U_{m%2B1} - Q U_m U_{n-1}=\frac{U_nV_m%2BU_mV_n}{2} \, F_{n%2Bm} = F_n F_{m%2B1} %2B F_m F_{n-1}=\frac{F_nL_m%2BF_mL_n}{2} \,
V_{n%2Bm} = V_n V_m - Q^m V_{n-m} \, L_{n%2Bm} = L_n L_m - (-1)^m L_{n-m} \,

Among the consequences is that U_{km} is a multiple of U_m, implying that U_n can be prime only when n is prime. Another consequence is an analog of exponentiation by squaring that allows fast computation of U_n for large values of n. These facts are used in the Lucas–Lehmer primality test.

Carmichael's theorem states that, in a Lucas sequence, all but finitely many of the numbers have a prime factor that does not divide any earlier number in the sequence (Yubuta 2001).

Specific names

The Lucas sequences for some values of P and Q have specific names:

Un(1,−1) : Fibonacci numbers
Vn(1,−1) : Lucas numbers
Un(2,−1) : Pell numbers
Vn(2,−1) : Companion Pell numbers or Pell-Lucas numbers
Un(1,−2) : Jacobsthal numbers
Un(3, 2) : Mersenne numbers 2n − 1
Vn(3, 2) : Numbers of the form 2n + 1, which include the Fermat numbers (Yubuta 2001).
Un(x,−1) : Fibonacci polynomials
Vn(x,−1) : Lucas polynomials

Applications

References

  1. ^ P. J. Smith, M. J. J. Lennon (1993). "LUC: A new public key system". Proceedings of the Ninth IFIP Int. Symp. on Computer Security: 103–117. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.1835. 
  2. ^ D. Bleichenbacher, W. Bosma, A. K. Lenstra (1995). "Some Remarks on Lucas-Based Cryptosystems". Lecture Notes in Computer Science 963: 386–396. doi:10.1007/3-540-44750-4_31. http://www.math.ru.nl/~bosma/pubs/CRYPTO95.pdf. 

See also